package oj;

public class LC343 {
    public int integerBreak(int n) {
        //以i结尾的dp[i]被拆分后的最大乘积
        int[] dp=new int[n+1];
        for(int i=2;i<=n;i++){
            for(int j=1;j<i;j++){
                dp[i]=Math.max(dp[i],Math.max(j*dp[i-j],j*(i-j)));//j是被拆分的值，可以选择被拆分为j后的i-j不再继续拆分，
                // 也可以选择继续拆分i-j，那就是dp[i-j]
            }
        }
        return dp[n];
    }
}
